home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / src / benchmarks / itc / sld / bsearch.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-05-12  |  2.0 KB  |  86 lines
  1. /* 
  2.  * bsearch.c --
  3.  *
  4.  *    Source code for the bsearch library routine.
  5.  *
  6.  * Copyright 1989 Regents of the University of California
  7.  * Permission to use, copy, modify, and distribute this
  8.  * software and its documentation for any purpose and without
  9.  * fee is hereby granted, provided that the above copyright
  10.  * notice appear in all copies.  The University of California
  11.  * makes no representations about the suitability of this
  12.  * software for any purpose.  It is provided "as is" without
  13.  * express or implied warranty.
  14.  * 
  15.  * $Sprite: /sprite/src/lib/c/stdlib/RCS/bsearch.c,v 1.4 89/05/18 17:09:12 rab Exp 
  16.  */
  17.  
  18. #ifndef lint
  19. static char rcsid[] = "$Header: /sprite/src/benchmarks/itc/sld/RCS/bsearch.c,v 1.2 92/05/12 15:00:58 kupfer Exp $";
  20. #endif /* not lint */
  21.  
  22.  
  23. #ifdef __STDC__
  24. #include <stdlib.h>
  25. #endif
  26.  
  27. #include <stdio.h>
  28. #include <sys/types.h>
  29.  
  30. #ifndef __STDC__
  31. #define const   /**/
  32. #endif
  33.  
  34.  
  35. /*
  36.  *----------------------------------------------------------------------
  37.  *
  38.  * bsearch --
  39.  *
  40.  *    Bsearch searches base[0] to base[n - 1] for an item that
  41.  *      matches *key.  The function cmp must return negative if its first
  42.  *      argument (the search key) is less that its second (a table entry),
  43.  *      zero if equal, and positive if greater.  Items in the array must
  44.  *      be in ascending order.  
  45.  *
  46.  * Results:
  47.  *    Returns a pointer to a matching item, or NULL if none exits.
  48.  *
  49.  * Side effects:
  50.  *    None.
  51.  *
  52.  *----------------------------------------------------------------------
  53.  */
  54.  
  55. char *
  56. bsearch(key, base, n, size, cmp)
  57.     const char *key;
  58.     const char *base;
  59.     size_t n;
  60.     size_t size;
  61. #ifdef __STDC__
  62.     int (*cmp)(const void *, const void *);
  63. #else
  64.     int (*cmp)();
  65. #endif
  66. {
  67.     const char *middle;
  68.     int c;
  69.  
  70.  
  71.     for (middle = base; n != 0;) {
  72.     middle += (n/2) * size;
  73.     if ((c = (*cmp)(key, middle)) > 0) {
  74.         n = (n/2) - ((n&1) == 0);
  75.         base = (middle += size);
  76.     } else if (c < 0) {
  77.         n /= 2;
  78.         middle = base;
  79.     } else {
  80.         return (char *) middle;
  81.     }
  82.     }
  83.     return NULL;
  84. }
  85.  
  86.